package com.zrrd.zuo.stralgo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author ywb
 * @Description:
 * @date 2023/4/18 22:26
 */
//全排列
public class PrintAllPermutations {
    public static List<String> permutation(String s){
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        Process(str,0,ans);
        return ans;
    }
    public static void Process(char[] str,int i,List<String> ans){
        if(i == str.length){
            ans.add(String.valueOf(str));
        }
        for (int j = i; j < str.length; j++) {
            swap(str,i,j);
            Process(str,i + 1,ans);
            swap(str,i,j);
        }
    }
    //无重复全排列 set过滤方法
    public static List<String> permutation1(String s){
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        HashSet<String> set = new HashSet<>();
        char[] str = s.toCharArray();
        Process1(str,0,set);
        for (String s1 : set) {
            ans.add(s1);
        }
        return ans;
    }
    public static void Process1(char[] str, int i, HashSet<String> set){
        if(i == str.length){
            set.add(String.valueOf(str));
        }
        for (int j = i; j < str.length; j++) {
            swap(str,i,j);
            Process1(str,i + 1,set);
            swap(str,i,j);
        }
    }
    //去除重复复 分支限界算法
    public static List<String> permutation2(String s){
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        Process2(str,0,ans);
        return ans;
    }
    public static void Process2(char[] str,int i,List<String> ans){
        if(i == str.length){
            ans.add(String.valueOf(str));
        }else {
            HashSet<Character> set = new HashSet();
            for (int j = i; j < str.length; j++) {
                if(!set.contains(str[j])){
                    set.add(str[j]);
                    swap(str,i,j);
                    Process2(str,i + 1,ans);
                    swap(str,i,j);
                }

            }
        }

    }
    public static List<String> permutation3(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        g2(str, 0, ans);
        return ans;
    }

    public static void g2(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(str));
        } else {
            boolean[] visited = new boolean[256];
            for (int i = index; i < str.length; i++) {
                if (!visited[str[i]]) {
                    visited[str[i]] = true;
                    swap(str, index, i);
                    g2(str, index + 1, ans);
                    swap(str, index, i);
                }
            }
        }
    }
    public static void swap(char[] str, int i, int j){
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }

    public static void main(String[] args) {
        String s = "aab";
        List<String> strings = permutation2(s);
        for (String string : strings) {
            System.out.println(string);
        }
    }
}
